/*
 * =====================================================================================
 *
 *       Filename:  SortProblem.cpp
 *
 *    Description:  排序算法的测试用例
 *
 *        Version:  1.0
 *        Created:  2011-10-28 10:02:31
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *        Company:
 *
 * =====================================================================================
 */

#include "SortProblem.h"
#include "gtest/gtest.h"

#define MAX_TEST_COUNT 100

//冒泡排序测试
TEST(bubbleSort, randArray)
{
    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        bubbleSort(A, 0, A.size() - 1);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }
}

//鸡尾酒排序
TEST(cocktailBubbleSort, randArray)
{
    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        cocktailBubbleSort(A, 0, A.size() - 1);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }
}

//选择排序测试
TEST(selectSort, randArray)
{
    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        selectSort(A, 0, A.size() - 1);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }
}

//插入排序测试
TEST(insertSort, randArray)
{
    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        insertSort(A, 0, A.size() - 1);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }
}

//适应性插入排序测试
TEST(insertSort2, randArray)
{
    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        insertSort2(A, 0, A.size() - 1);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }
}

//Shell排序测试
TEST(shellSort, randArray)
{
    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        shellSort(A, 0, A.size() - 1);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }
}

//计数排序测试
TEST(countSort, randPositiveArray)
{
    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genPositiveRandVector(A, i);
        countSort(A, 0, A.size() - 1, 32);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }
}

//快速排序测试
TEST(quickSort, hoarePartition)
{
    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        quickSort(A, 0, A.size() - 1, hoarePartition);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "quickSort end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        quickSortLoop(A, 0, A.size() - 1, hoarePartition);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "quickSortLoop end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        quickSortInsert(A, 0, A.size() - 1, hoarePartition);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "quickSortInsert end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        quickSortMedianOfThreeAndInsert(A, 0, A.size() - 1, hoarePartition);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "quickSortMedianOfThreeAndInsert end." << std::endl;
}

TEST(quickSortLoop, clrsPartition)
{
    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        quickSort(A, 0, A.size() - 1, clrsPartition);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "quickSort end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        quickSortLoop(A, 0, A.size() - 1, clrsPartition);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "quickSortLoop end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        quickSortInsert(A, 0, A.size() - 1, clrsPartition);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "quickSortInsert end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        quickSortMedianOfThreeAndInsert(A, 0, A.size() - 1, clrsPartition);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "quickSortMedianOfThreeAndInsert end." << std::endl;
}

TEST(quickSort, threeWayPartition)
{
    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        quickSort(A, 0, A.size() - 1, threeWayPartition);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "quickSort end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        quickSortLoop(A, 0, A.size() - 1, threeWayPartition);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "quickSortLoop end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        quickSortInsert(A, 0, A.size() - 1, threeWayPartition);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "quickSortInsert end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        quickSortMedianOfThreeAndInsert(A, 0, A.size() - 1, threeWayPartition);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "quickSortMedianOfThreeAndInsert end." << std::endl;
}

TEST(mergeSort, mergeOrigin)
{
    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSort(A, 0, A.size() - 1, mergeOrigin);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSort end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSortWithInsert(A, 0, A.size() - 1, mergeOrigin);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSortWithInsert end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSortLoop(A, 0, A.size() - 1, mergeOrigin);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSortLoop end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSortLoopWithInsert(A, 0, A.size() - 1, mergeOrigin);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSortLoopWithInsert end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSortWithCopy(A, 0, A.size() - 1);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSortWithCopy end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSortWithCopyInsert(A, 0, A.size() - 1);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSortWithCopyInsert end." << std::endl;

}
//测试 归并排序
TEST(mergeSort, mergeUseMax)
{
    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSort(A, 0, A.size() - 1, mergeUseMax);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSort end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSortWithInsert(A, 0, A.size() - 1, mergeUseMax);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSortWithInsert end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSortLoop(A, 0, A.size() - 1, mergeUseMax);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSortLoop end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSortLoopWithInsert(A, 0, A.size() - 1, mergeUseMax);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSortLoopWithInsert end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSortWithCopy(A, 0, A.size() - 1);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSortWithCopy end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSortWithCopyInsert(A, 0, A.size() - 1);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSortWithCopyInsert end." << std::endl;

}
TEST(mergeSort, mergeExpand)
{
    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSort(A, 0, A.size() - 1, mergeExpand);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSort end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSortWithInsert(A, 0, A.size() - 1, mergeExpand);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSortWithInsert end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSortLoop(A, 0, A.size() - 1, mergeExpand);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSortLoop end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSortLoopWithInsert(A, 0, A.size() - 1, mergeExpand);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSortLoopWithInsert end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSortWithCopy(A, 0, A.size() - 1);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSortWithCopy end." << std::endl;

    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        mergeSortWithCopyInsert(A, 0, A.size() - 1);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }

    std::cout << "mergeSortWithCopyInsert end." << std::endl;

}

//堆排序测试
TEST(heapSort, randArray)
{
    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genRandVector(A, i);
        heapSort(A, 0, A.size() - 1);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }
}

//二进制快速排序
TEST(quickSortUseBinary, randArray)
{
    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genPositiveRandVector(A, i);
        quickSortUseBinary(A, 0, A.size() - 1);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }
}

//MSD基数排序
TEST(mostSignificantDigitSort, randArray)
{
    for (int i = 0; i <= MAX_TEST_COUNT; ++i) {
        std::vector<int> A;
        genPositiveRandVector(A, i);
        mostSignificantDigitSort(A, 0, A.size() - 1);
        EXPECT_TRUE(isVectorOrdered(A) == true);
    }
}

//threeWayMsd基数排序
TEST(threeWayMsdSort, randArray)
{
    std::vector<std::string> A;
    A.push_back("I");
    A.push_back("am");
    A.push_back("good");
    A.push_back("man");
    A.push_back("and");
    A.push_back("like");
    A.push_back("beauty");
    A.push_back("woman");
    std::copy(A.begin(), A.end(), std::ostream_iterator<std::string>(std::cout, " "));
    std::cout << std::endl;
    threeWayMsdSort(A, 0, A.size() - 1);
    std::copy(A.begin(), A.end(), std::ostream_iterator<std::string>(std::cout, " "));
    std::cout << std::endl;
    std::cout << (int)'a' << " "
              << (int)'z' << " "
              << (int)'A' << " "
              << (int) 'Z' << std::endl;
}

int main(int argc, char *argv[])
{
    testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}
